The present invention relates to processing of raster scan images, and more particularly relates to processing of raster scan images of rectilinear symbols such as PDF symbols or bar code symbols.
Optical scanners are widely used for reading data included by symbols on various items. One common application of optical scanning is in reading of bar code symbols such as Universal Product Code (xe2x80x9cUPCxe2x80x9d) symbols. These scanners typically operate by directing a beam of light from a source such as a laser onto the object bearing the symbol and detecting the intensity of the reflected light. The scanner typically incorporate optical elements which focus the beam of light to a relatively small spot at the object bearing the symbol and can move the optical elements so as to sweep the spot of light across the object in a series of parallel lines referred to as xe2x80x9crasterxe2x80x9d. These scanners also include a photodetector such as a photodiode or phototransistor which receives the light reflected from the object. As the spot of light moves over the object and encounters light and dark areas on the surface of the object, the amount of light reflected to the photodetector varies and the electrical signal produced by the photodetector varies correspondingly. These variations in the electrical signal from the photodetector typically are converted into digital signals having a first value, (e.g., 0) when the spot of light is focused on a point having high reflectivity and having a second, different value (e.g., 1) when the spot is focused on a point having low reflectivity. Thus, the scanner produces a series of digital values representing the reflectivity of the object at a series of points along each of the lines in the raster. Other scanners use different physical elements to provide a similar series of values for reflectivity along raster scan lines.
This data is then converted into information which represents the data encoded by the symbol using a computer programmed to recognize certain patterns in the data as representing certain information encoded by the symbol. The pattern recognition problem is complicated by the fact that the raster used to scan the symbol may lie at an arbitrary orientation with respect to the horizontal and vertical directions of the symbol. For example, a conventional one-dimensional bar code symbol 10 (FIG. 1) has a horizontal direction denoted by Xs and a vertical direction denoted by the arrow Ys. The symbol includes a series of vertical dark and light bars. The information carried by the symbol is encoded in the widths of these bars. For example, a dark bar 12 one unit wide followed by a light bar 14 one unit wide and a dark bar 16 three units wide may denote a numeral xe2x80x9c3xe2x80x9d whereas other sets of bars having different widths may denote other characters. If the symbol is scanned using a raster having scan lines 18 perfectly parallel to the horizontal direction of the symbol, the widths of the various bars will appear in the data as the lengths of series of ones and zeros representing light and dark areas. For example, bar 12 may appear as a series of 10 ones; light bar 14 may appear as a series of 10 zeros and dark bar 16 may appear as a series of 30 ones in succession. The other bars constituting the symbol will be represented in the same manner. If the horizontal or line direction of the raster is drastically misaligned with the horizontal direction of the symbol, the symbol cannot be read. For example, none of the scanning lines in raster 20 intercepts all of the bars in the symbol. However, if the horizontal direction of the raster is only slightly misaligned with the symbol, the symbol can still be read. For example, scan line 22a of raster 22 will intercept all of the bars in the symbol. Thus, the data representing the light and dark regions encountered along line 22a still includes the same series of light and dark regions which would be encountered along perfectly aligned scan line 18. The bars will still be represented by series of ones and zeros and the lengths of these series will still be proportional to the widths of the bar. For example, bar 12 may be represented as a series of 12 ones; light space 14 may appear as a series of 12 zeros and bar 16 may appear as a series of 36 ones. Although the absolute lengths of these series differ from the lengths which would be recorded for a perfectly aligned raster, the proportions of these series relative to one another do not change. Therefore, the computer can accurately decode the symbol based on the data acquired using raster 22. Typical scanners used for decoding one-dimensional bar codes gather data using rasters arranged at a few different dispositions as, for example, three rasters having their respective horizontal directions at 60 degree angles to one another. One of these rasters will have its horizontal direction aligned well enough with the horizontal direction of the symbol to provide meaningful data. The system discards the useless data generated by the other rasters.
There is a growing trend towards the use of two-dimensional symbols which include plural horizontal rows of light and dark regions. For example, the symbol 25 depicted in FIG. 2 is a PDF417 symbol having a horizontal direction Xs and a vertical direction Ys, and having nine horizontal rows 27 of light and dark areas. Each horizontal row of light and dark areas includes different information. Such a symbol can carry more information in a given space than a one-dimensional bar code. However, alignment of the horizontal direction of the raster with the horizontal direction of the symbol is far more critical in the case of a two-dimensional code. Thus, where the raster is perfectly aligned with the symbol, it will include at least one scanning line aligned with each horizontal row 27 of the symbol. For example, raster line 26a extends through the topmost row 27a areas in symbol 24, but does not extend through any other row of the symbol. Similarly, line 26b of the same raster extends through the second row 27b of the symbol and so on. Line 28a of a misaligned raster, which is skewed with respect to the symbol, will not include the same pattern of light and dark areas as any of the perfectly aligned scan lines 26. To provide meaningful information from a two-dimensional symbol, a raster must be have its horizontal direction aligned to within a few degrees with the horizontal direction of the symbol. To read a two-dimensional symbol presented at a random orientation using the trial-and-error approach used with one-dimensional symbols, the system would have to generate scores of rasters, and try to decipher data from all of these rasters, in order to be sure of obtaining data from one raster having its horizontal direction aligned well enough with the horizontal direction of the symbol. This typically is not practical.
As described, for example, in Shellhammer et al., U.S. Pat. No. 5,523,552, it has been proposed to scan a two-dimensional rectilinear symbol such as a PDF symbol using a plurality of rasters disposed at different known dispositions. The system calculates the skew angle between the vertical direction of each raster and the vertical direction of the symbol based upon the data found in each scan. From these skew angles, the system determines the disposition of the symbol in the frame of reference of the scanner apparatus. The system then generates a raster having its horizontal direction aligned with the horizontal directions of the symbol, and sweeps the light beam thorough such raster. This approach requires repetitive scanning of the symbol, which in turn limits the speed of operation of the system. Moreover, it requires a scanner which is physically capable of generating a real raster at an arbitrary disposition, which in turn requires a more complex scanning system.
Swartz et al., U.S. Pat. No. 5,637,851 and Wevelseip, U.S. Pat. No. 4,691,367 disclose systems in which data captured by a raster scan is stored as a two-dimensional bit map in a computer memory. Such a two-dimensional bit map has individual bits of data representing the reflectivity of individual dots or xe2x80x9cpixelsxe2x80x9d stored in a two-dimensional array within a computer memory. One dimension of the array corresponds to the vertical dimension of the real raster used to capture the data, whereas the other dimension of the array corresponds to location in the horizontal direction, along the scanning lines of such raster. For example, the reflectivity of the spot on the symbol at location X along scanning line Y will be represented by the data stored in the memory at location X, Y. The system generates virtual scan lines by calculating the addresses in memory corresponding to the locations of pixels which would fall along virtual scanning lines disposed at arbitrarily-selected angles to the real scanning lines. For example, a sequence of data at locations (X, Y); (X+1, Y+1); (X+2, Y+2) represents a scan line at an angle of 45xc2x0 to the real scan lines. The system reads out the data in such a sequence of addresses. When the system finds an arbitrary angle which yields a xe2x80x9cgoodxe2x80x9d virtual scan line, i.e., a sequence of intelligible data corresponding to a possible symbol, the system generates additional virtual scan lines parallel to the first good scan line.
Such a system requires a sizable memory for storing all of the data and requires considerable computational effort to generate all the virtual scan lines, retrieve the data corresponding to the virtual scan lines and detect an intelligible symbol by trial and error. Moreover, real raster scan data has different resolutions in horizontal and vertical directions. A typical scan may include a few hundred horizontal lines covering the entire area scanned and hence has a relatively coarse resolution in the vertical direction. However, the scanning system typically can detect changes in reflectivity at several thousand points along the length of each scan line and hence has a relatively fine resolution in the horizontal direction. Some of this fine horizontal resolution typically is lost in the bit mapping approach.
It is desirable to represent the information contained in a scanned image as run length encoded data. In run length encoding, the data is presented as a series of numbers denoting the lengths of xe2x80x9crunsxe2x80x9d or series of pixels all having the same reflectivity, rather than by a series of identical data bits. For example, a sequence of 64 pixels all having the same reflectivity can be denoted by the digital number 64 (10000 in binary) rather than by a string of 64 ones in sequence. Alternatively, the number may specify the location of the end of the run relative to a fixed datum point. Run-length encoding greatly reduces the amount of data which must be handled during operation of the system. The scanner can produce run length encoded data during the scanning operation. However, the bit map operations used in the ""851 and ""367 patents cannot be performed on data in run-length encoded format.
Tsujimoto et al., U.S. Pat. No. 4,878,124 and Barski, U.S. Pat. No. 4,866,784 are directed to systems for rotating images other than rectilinear symbols as, for example, images of text in an optical character recognition system. These systems use run-length encoded data to determine the skew angles of edges, but do not attempt to rotate the data in run-length encoded form. Cayhill, III et al., U.S. Pat. No. 4,792,981 discloses a system involving a rather complex series of computations of xe2x80x9cvisible and invisible vectorsxe2x80x9d within a run-length encoded image and seeks to transform the run-length encoded data into a different frame of reference using criteria based on those vectors. Zhu et al., U.S. Pat. No. 5,581,635 describes a system for rotating run-length encoded data such as an image of text. That system however is only capable of rotating the run-length encoded data through pre-determined rotation angles having tangents which are rational numbers. These systems apparently have not been used in processing images of rectilinear symbols such as one-dimensional bar codes, PDF symbols and other two-dimensional code symbols. Thus, despite considerable effort in the art, there still remains a need for methods and apparatus which can decode a rectilinear symbol, particularly a two-dimensional symbol presented at an arbitrary, unknown angle to a raster scanner. In particular, there remains a need for a system which can function in real time, while an image is being scanned, using a limited of computational power and memories of limited size, but which can operate on high-resolution scanned images without loss of resolution.
The problems associated with processing scanned images are aggravated by factors such as cost and speed requirements. The task of translating scanned data into intelligible form may be performed by a computer associated with the scanner, rather than by a separate computer which may receive the data from the scanner. For example, in a point-of-sale system using a personal computer, conversion of the scanned image to a numeric data desirably is performed by a dedicated computer of limited capacity incorporated in the scanner, rather than by the central processing unit of the personal computer. Such a dedicated computer may be mounted on a circuit panel within the scanner itself, or incorporated in a plug-in interface card sold with the scanner and mounted in a computer which receives the scanned data. The load on such a dedicated computer must be limited if it is to convert the scanned data rapidly. Thus, despite all of the progress which has been made in development of low-cost, powerful computer hardware, it is still important to provide methods which minimize the computational load on the computer hardware. Even where the decoding operation is handled by a powerful computer used for other purposes, such as the CPU of a retail point-of-sale system, it is still important to minimize the computational load on the system. Moreover, the amount of data which may be handled and stored is limited either by the available on-board memory, or by the communication bandwidth between a scanner and a separate computer.
One aspect of the present invention provides a method of acquiring and processing data defining an image of a symbol having vertical and horizontal directions and having one or more horizontal rows of dark and light regions denoting information encoded in the symbol. The method according to this aspect of the invention desirably includes the steps of acquiring raw scan data representing an image of a region including the symbol using a real raster having real horizontal and vertical directions in a real raster frame of reference and having real scan lines extending in the real horizontal direction. The method further includes the step of run length encoding the raw scanned data so as to provide run length encoded data including transition point data denoting the locations of transitions between light and dark on the real scan lines. The method further includes the step of determining orientations of one or more directions of the symbol relative to the directions of the real raster and, using a transform based upon these orientations, transforming only the transition point data into a virtual scan frame of reference having virtual horizontal and vertical directions aligned with the horizontal and vertical directions of the symbol. Typically, the transforming step includes the step of mapping the transition data points onto virtual scan lines extending in the virtual horizontal direction.
Because only the transition point data is transformed, the amount of data which must be processed in the transformation step is markedly less than that which would be required for transformation of a full bit mapped image. The method can operate directly on run length encoded data, without converting the data back to a full bit map. Moreover, because the method can provide run length encoded data in the virtual scan frame of reference as its output. This run length encoded data is readily processed in further computational steps. Desirably, the step of determining orientations of the directions of the symbols relative to the directions of the real raster is performed by examining data derived from the real scan data as, for example, by examining the run length encoded real scan data to detect a skew angle between the direction of the symbol and the real horizontal direction or real vertical direction of the real raster.
The step of mapping the transition points onto virtual scan lines extending in the virtual horizontal direction desirably includes the step of finding crossing points of the real scan lines and virtual scan lines in a common frame of reference. Each transition point is associated with a crossing point adjacent to the transition point on the real scan line which incorporates such transition point. Each transition point is also associated with a virtual scan line which incorporates the crossing point associated with such transition point. The method further includes the step of determining a distance between each transition point and the associated crossing point along the real scan line incorporating the transition point and the associated crossing point. The distance along the real scan line obtained in the determining step is transformed to a distance along the associated virtual scan line. The system derives transformed data denoting the locations of the transition point on the virtual scan line associated with such transition point at the calculated distance, along the vertical scan line from the associated crossing point.
The method may include the steps of determining crossing locations of the scanning lines of the real raster and the virtual scanning lines and segmenting the real and virtual scanning lines into a plurality of segments, each such segment extending between two adjacent crossing points on the scan line which includes the segment. Thus, each real scan line segment is associated with a virtual scan line segment having a common crossing point with the real scan line segment. The transition points from each real scan line segment are mapped onto the virtual scan line segment associated with that real scan line segment so that the distance between the common crossing point and each transition point on the virtual scan line segment is proportional to the distance between the common crossing point and the same transition point on the real scan line segment. The use of a mapping based upon crossing points minimizes cumulative errors in the system caused by inaccuracies in determination of the skew angle.
In a method according to a further embodiment of the invention, each virtual scan line segment may be associated with two real scan line segments which have common crossing points at opposite ends of the virtual scan line segment. Transition points may be mapped onto the virtual scan line segment from both of these real scan line segments. The method may further include the step of comparing the locations of transition points mapped onto a particular virtual scan line segment from different real scan line segments to one another and deriving combined transition point data based upon such comparison. For example, the method may include the step of detecting two transition points mapped from different real scan lines and falling at less than a predetermined threshold distance from one another along the virtual scan line segment, and deriving a single transition point on the virtual scan line segment from such two or more transition points. As further discussed below, such a method further minimizes the effects of noise in the raw scan data and also minimizes the effects of digitization errors.
A further aspect of the present invention provides methods of processing data defining an image of a rectilinear symbol having linear features extending in vertical and horizontal directions. The method according to this aspect of the invention includes the steps of providing incoming image data representing a raster scan of the symbol having horizontal and vertical directions, the directions of the raster being in an unknown orientation relative to the directions of the symbol. The method further includes the step of examining the incoming image data to detect one or more linear features of the symbol, and determining the orientation of each such linear features relative to the frame of reference of the raster and selecting from the detected feature or features a feature extending at an angle of less than 45xc2x0 to the horizontal direction of the raster. The method further includes the step of determining a skew angle between a direction of the symbol and a direction of the raster based upon the orientation of the selected feature. The method according to this aspect of the invention may further include the step of transforming the incoming image data based upon the skew angle to a virtual raster frame of reference having a horizontal direction aligned with the direction of the selected linear feature of the symbol.
Methods according to this aspect of the invention incorporate the realization that a more accurate estimate of the true skew angle can be obtained by detecting the inclination of a nearer-horizontal feature i.e., a feature of the symbol which lie close to the orientation of the raster lines, as opposed to near-vertical edges which are close to perpendicular to the raster lines of the scan. Methods according to this aspect of the invention can be used in conjunction with methods according to the foregoing aspects of the invention. Thus, the incoming image data may be the real raster scan data or the run length encoded real raster scan data, and the step of transforming the image data may be performed using the virtual scan and crossing points as discussed above. The skew angle determination typically is based on the assumption that the true horizontal direction of the symbol lies at less than 45xc2x0 to the horizontal direction of the raster. Typically, methods according to this aspect of the invention are performed using plural sets of incoming image data each representing a raster scan of the symbol at a different orientations. The examining, selecting and transforming steps desirably are performed independently for each set of incoming image data. The plural sets of incoming image data may include at least three sets of incoming image data representing rasters having horizontal directions oblique to one another as, for example, at angles of 60xc2x0 to one another. Thus, at least one set of incoming image data will have a horizontal direction oriented at an angle of less than 45xc2x0 to the horizontal direction of the symbol and hence will yield intelligible data when transformed based upon the skew angle derived for that set of incoming image data.
Preferably, the step of examining the incoming image data to detect edges of the symbol includes the step of evaluating a function of location in the raster frame of reference associated with the incoming data and an assumed skew angle over a plurality of points represented by the incoming image data and over a plurality of assumed skew angles for each such point. The function desirably has the property that points lying on a line in the symbol will yield the same value of the function when the assumed skew angle is equal to an angle between the line and a direction, of the raster frame of reference. Desirably, the step of examining the incoming image data includes the step of counting the number of points which yield particular values of the function at each assumed skew angle and selecting as the skew angle an angle equal to the assumed skew angle associated with the highest count of points. For example, the function may be a Hough transform xcfx81 such that:
xcfx81=x cos xcex8+y sin xcex8
Where X is the coordinate of the point in the horizontal direction of the raster;
Y is the coordinate of the point in the vertical direction of the raster and
xcex8 is the assumed skew angle.
As further discussed below, because a rectilinear symbol has large numbers of transition points lying along straight lines extending in the vertical and horizontal directions of the symbol, large numbers of these points will fall on the same line in the raster frame of reference, and give the same value of xcfx81 when the assumed skew angle xcex8 is equal to the actual skew angle. Thus, by selecting the assumed skew angle xcex8 which gives the largest number of points having the same value of xcfx81, the system selects a skew angle corresponding to the real skew angle between a direction of the symbol and a direction of the raster.
Preferably, the step of examining the incoming data further includes the step of testing transition points in the incoming image data to determine spacings between these points and excluding from the step of excluding the Hough transform or other fraction those points in the incoming data representing transitions disposed at less than a preselected threshold distance from other transitions. This step will exclude some transition points representing within the interior of the symbol, and simplifies the skew angle calculation without serious loss of accuracy.
Still further aspects of the invention include equipment operable to perform the aforesaid methods and programming elements operative to actuate a programmable computer to perform such methods. The programming elements incorporate a data storage medium such as a disc, tape, programmable read only memory (xe2x80x9cPROMxe2x80x9d) or other medium capable of storing information and program information stored therein, the program information including instructions operative to actuate a computer to perform methods as aforesaid.
These and other objects, features and advantages of the present invention will be more readily apparent from the detailed description of the preferred embodiments set forth below taken in conjunction with the accompanying drawings.